// https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/

// 算法思路总结：
// 1. 问题转化为寻找和为sumAll-x的最长子数组
// 2. 使用滑动窗口维护和小于等于target的区间
// 3. 记录满足和等于target的最大窗口长度
// 4. 最小操作次数为总长度减去窗口长度
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <climits>
#include <numeric>

class Solution 
{
public:
    int minOperations(vector<int>& nums, int x) 
    {
        int sumAll = accumulate(nums.begin(), nums.end(), 0);
        int target = sumAll - x, n = nums.size();

        if (sumAll < x) return -1;
        if (sumAll == x) return n;

        // 维护一段区间，使其和小于等于target
        int len = INT_MIN, sum = 0;
        for (int l = 0, r = 0 ; r < n ; r++)
        {
            sum += nums[r];
            while (sum > target)
            {
                sum -= nums[l];
                l++;
            }

            if (sum == target)
                len = max(len, r - l + 1);
        }

        return len == INT_MIN ? -1 : n - len;
    }
};

int main()
{
    vector<int> v1 = {1,1,4,2,3}, v2 = {5,6,7,8,9};
    int x1 = 5, x2 = 4;
    
    Solution sol;
    cout << sol.minOperations(v1, x1) << endl;
    cout << sol.minOperations(v2, x2) << endl;

    return 0;
}